package cn.edu.neu.softlab.jason.offer.jianzhioffer.datastructure;

import cn.edu.neu.softlab.jason.offer.jianzhioffer.datastructure.util.LinkedList;
import cn.edu.neu.softlab.jason.offer.jianzhioffer.datastructure.util.LinkedNode;

/**
 * 剑指offer-面试13
 * 在O(1)时间内删除链表的结点
 * 给定一个单项链表的头指针和一个结点指针，定义一个函数
 * 在O(1)时间内删除该结点。链表的定义见LinkedNode
 */
public class Mianshi13 {
    public static void main(String[] args) throws Exception {
        LinkedNode head = new LinkedNode(1);
        LinkedNode node2 = new LinkedNode(2);
        LinkedNode node3 = new LinkedNode(3);
        LinkedNode node4 = new LinkedNode(4);
        LinkedNode node5 = new LinkedNode(3);
        LinkedList.addToTail(head, node2);
        LinkedList.addToTail(head, node3);
        LinkedList.addToTail(head, node4);
        head = deleteNodeInO1(head, node2);
        head = deleteNodeInO1(head, head);
        head = deleteNodeInO1(head, node4);
        deleteNodeInO1(head, node5);
    }

    public static LinkedNode deleteNodeInO1(LinkedNode head, LinkedNode node) throws Exception {
        if (node == head) {
            head = head.next;
            node.next = null;
            return head;
        }
        if (node.next != null) {
            node.value = node.next.value;
            LinkedNode tmp = node.next.next;
            node.next.next = null;
            node.next = tmp;
            return head;
        }
        LinkedNode cur = head;
        while (cur != null && cur.next != node) {
            cur = cur.next;
        }
        if (cur == null) {
            throw new Exception("链表中无此结点");
        }
        cur.next = null;
        return head;
    }
}
